{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 13.4 Deletion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 13.4-1\n",
    "\n",
    "> Argue that after executing RB-DELETE-FIXUP, the root of the tree must be black."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Case 1, transform to 2, 3, 4.\n",
    "\n",
    "Case 2, if terminates, the root of the subtree (the new $x$) is set to black.\n",
    "\n",
    "Case 3, transform to 4.\n",
    "\n",
    "Case 4, the root (the new $x$) is set to black."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 13.4-2\n",
    "\n",
    "> Argue that if in RB-DELETE both $x$ and $x.p$ are red, then property 4 is restored by the call to RB-DELETE-FIXUP$(T, x)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Will not enter the loop, $x$ is set to black."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 13.4-3\n",
    "\n",
    "> In Exercise 13.3-2, you found the red-black tree that results from successively inserting the keys $41, 38, 31, 12, 19, 8$ into an initially empty tree. Now show the red-black trees that result from the successive deletion of the keys in the order $8, 12, 19, 31, 38, 41$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](img/13.4-3_1.png)\n",
    "\n",
    "Delete 8:\n",
    "\n",
    "![](img/13.4-3_2.png)\n",
    "\n",
    "Delete 12:\n",
    "\n",
    "![](img/13.4-3_3.png)\n",
    "![](img/13.4-3_4.png)\n",
    "![](img/13.4-3_5.png)\n",
    "\n",
    "Delete 19:\n",
    "\n",
    "![](img/13.4-3_6.png)\n",
    "![](img/13.4-3_7.png)\n",
    "\n",
    "Delete 31:\n",
    "\n",
    "![](img/13.4-3_8.png)\n",
    "![](img/13.4-3_9.png)\n",
    "\n",
    "Delete 38:\n",
    "\n",
    "![](img/13.4-3_10.png)\n",
    "![](img/13.4-3_11.png)\n",
    "\n",
    "Delete 41."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 13.4-4\n",
    "\n",
    "> In which lines of the code for RB-DELETE-FIXUP might we examine or modify\n",
    "the sentinel $T.nil$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Line 1, 2."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 13.4-5\n",
    "\n",
    "> In each of the cases of Figure 13.7, give the count of black nodes from the root of the subtree shown to each of the subtrees $\\alpha, \\beta, \\dots, \\zeta$, and verify that each count remains the same after the transformation. When a node has a color attribute $c$ or $c'$, use the notation count$(c)$ or count$(c')$ symbolically in your count."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\dots$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 13.4-6\n",
    "\n",
    "> Professors Skelton and Baron are concerned that at the start of case 1 of RBDELETE-FIXUP, the node $x.p$ might not be black. If the professors are correct, then lines 5–6 are wrong. Show that $x.p$ must be black at the start of case 1, so that the professors have nothing to worry about."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since $w$ is red, based on property 4, $x.p$ must be black."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 13.4-7\n",
    "\n",
    "> Suppose that a node $x$ is inserted into a red-black tree with RB-INSERT and then is immediately deleted with RB-DELETE. Is the resulting red-black tree the same as the initial red-black tree? Justify your answer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "No. \n",
    "\n",
    "![](img/13.4-7_1.png)\n",
    "\n",
    "Insert 3:\n",
    "\n",
    "![](img/13.4-7_2.png)\n",
    "\n",
    "Delete 3:\n",
    "\n",
    "![](img/13.4-7_3.png)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
